use std::cmp::{Eq, PartialEq};
use std::collections::{HashMap, HashSet};
use std::fmt::Display;
use std::hash::{Hash, Hasher};
use std::ops::Deref;
use std::{cell::RefCell, rc::Rc};

use crate::stools::{random_array, random_num};

#[derive(Clone)]
pub struct RcLink(pub Option<Rc<RefCell<Node>>>);
impl Deref for RcLink {
    type Target = Option<Rc<RefCell<Node>>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl Eq for RcLink {}
impl PartialEq for RcLink {
    fn eq(&self, other: &Self) -> bool {
        let lp = self.as_deref().map(|node| node.as_ptr());
        let rp = other.as_deref().map(|node| node.as_ptr());
        lp == rp
    }
}
impl Hash for RcLink {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        if self.is_none() {
            0.hash(state);
        } else {
            self.as_ref().map(|node| node.as_ptr().hash(state));
        }
    }
}
impl RcLink {
    pub fn new(elem: i32) -> Self {
        Self(Some(Rc::new(RefCell::new(Node::new(elem)))))
    }

    pub fn move_step(&self, mut step: usize) -> Self {
        if self.is_none() {
            return RcLink(None);
        }

        let mut link = self.clone();
        while step > 0 && link.is_some() {
            if let RcLink(Some(node)) = link {
                link = node.borrow().next.clone();
            }
            step -= 1;
        }

        link
    }
}

impl Display for RcLink {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_none() {
            write!(f, "None")?;
            return Ok(());
        }

        self.0
            .as_ref()
            .map(|node| write!(f, "[{} -> ]", node.borrow().elem).unwrap());

        Ok(())
    }
}

pub struct Node {
    pub elem: i32,
    pub next: RcLink,
}
impl Node {
    fn new(elem: i32) -> Self {
        Self {
            elem,
            next: RcLink(None),
        }
    }
}

pub struct RcList {
    pub head: RcLink,
}
impl Display for RcList {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.head.is_none() {
            write!(f, "None")?;
            return Ok(());
        }

        let mut link = self.head.clone();
        let (_, tail, enter) = self.iter_list();

        write!(f, "[")?;
        while link != tail {
            let node = link.as_ref().unwrap();
            if link == enter {
                write!(f, "(")?;
            }
            write!(f, "{} -> ", node.borrow().elem)?;
            link = link.move_step(1);
        }
        tail.as_ref()
            .map(|node| write!(f, "{} -> ", node.borrow().elem).unwrap());
        enter
            .as_ref()
            .map(|node| write!(f, "({} -> ...", node.borrow().elem).unwrap());

        write!(f, ")]")?;
        Ok(())
    }
}

impl RcList {
    pub fn new() -> Self {
        Self { head: RcLink(None) }
    }

    pub fn push(&mut self, elem: i32) -> &mut Self {
        if self.head.is_none() {
            self.head = RcLink::new(elem);
            return self;
        }

        self.tail()
            .0
            .map(|node| node.borrow_mut().next = RcLink::new(elem));

        self
    }

    pub fn from_array(&mut self, arr: &[i32]) -> &mut Self {
        for elem in arr {
            self.push(*elem);
        }
        self
    }

    fn idx(&self, mut index: usize) -> RcLink {
        if self.head.is_none() {
            return RcLink(None);
        }

        let mut link = self.head.clone();
        while index > 0 && link.is_some() {
            if let RcLink(Some(node)) = link {
                link = node.borrow().next.clone();
            }

            index -= 1;
        }

        link
    }

    pub fn tail(&self) -> RcLink {
        let (_len, tail, _enter) = self.iter_list();
        tail
    }

    fn enter(&self) -> RcLink {
        let (_len, _tail, enter) = self.iter_list();
        enter
    }

    fn len(&self) -> usize {
        let (len, _tail, _enter) = self.iter_list();
        len
    }

    fn append<'l, 's>(&'s mut self, other: &'l RcLink) -> &'s Self
    where
        'l: 's,
    {
        if self.head.is_none() {
            self.head = RcLink(other.0.clone());
            return self;
        }

        self.tail()
            .0
            .map(|node| node.borrow_mut().next = RcLink(other.0.clone()));

        self
    }

    fn iter_list(&self) -> (usize, RcLink, RcLink) {
        if self.head.is_none() {
            return (0, RcLink(None), RcLink(None));
        }
        let mut fast = self.head.clone();
        let mut slow = self.head.clone().move_step(1);
        let mut tail: RcLink = self.head.clone();

        if slow.is_none() {
            return (1, tail, slow);
        }

        fast = fast.move_step(2);
        if fast.is_none() {
            return (2, slow, fast);
        }

        let mut len = 1;
        while fast != slow {
            fast = fast.move_step(2);
            if fast.is_none() {
                while slow.is_some() {
                    len += 1;
                    tail = slow.clone();
                    slow = slow.move_step(1);
                }
                return (len, tail, fast);
            }
            len += 1;
            slow = slow.move_step(1);
        }

        fast = self.head.clone();
        len = 0;
        while fast != slow {
            len += 1;
            fast = fast.move_step(1);
            slow = slow.move_step(1);
        }
        fast = fast.move_step(1);
        len += 1;
        while fast != slow {
            len += 1;
            tail = fast.clone();
            fast = fast.move_step(1);
        }

        (len, tail, slow)
    }

    /// 快慢指针
    fn ring_enter(&self) -> RcLink {
        let (.., tail) = self.iter_list();
        tail
    }

    fn iter_list_hashmap(&self) -> (usize, RcLink, RcLink) {
        if self.head.is_none() {
            return (0, RcLink(None), RcLink(None));
        }
        let mut len = 0;
        let mut set: HashSet<RcLink> = HashSet::new();
        let mut tail: RcLink = self.head.clone();
        let mut enter: RcLink = self.head.clone();
        let mut node;

        while enter.is_some() {
            if set.contains(&enter) {
                break;
            }
            node = enter.0.unwrap();
            set.insert(RcLink(Some(node.clone())));

            len += 1;
            tail = RcLink(Some(node.clone()));
            enter = node.borrow().next.clone();
        }

        (len, tail, enter)
    }

    /// 集合
    fn ring_enter_hashset(&self) -> RcLink {
        let (.., enter) = self.iter_list_hashmap();
        enter
    }
}

fn nonring_list_cross(mut l1: RcLink, l1_len: usize, mut l2: RcLink, l2_len: usize) -> RcLink {
    if l1_len < l2_len {
        l2.move_step(l2_len - l1_len);
    } else {
        l1.move_step(l1_len - l2_len);
    }

    while l1 != l2 {
        l1 = l1.move_step(1);
        l2 = l2.move_step(1);
    }
    return l1;
}

fn ring_list_cross(l1: RcLink, l1_enter: RcLink, l2: RcLink, l2_enter: RcLink) -> RcLink {
    // 1. 在环外相交，可以把有环链表看成到入口节点的无环链表
    let mut link1 = l1.clone();
    let mut link2 = l2.clone();
    let mut n: i32 = 0;
    while link1 != l1_enter {
        n += 1;
        link1 = link1.move_step(1);
    }
    while link2 != l2_enter {
        n -= 1;
        link2 = link2.move_step(1);
    }

    link1 = l1.clone();
    link2 = l2.clone();
    if n < 0 {
        link2 = link2.move_step(-n as usize);
    } else {
        link1 = link1.move_step(n as usize);
    }

    while link1 != l1_enter && link2 != l2_enter {
        if link1 == link2 {
            return link1;
        }
        link1 = link1.move_step(1);
        link2 = link2.move_step(1);
    }

    // 2. 入口节点在环内，可以不是同一个节点，在环内循环一定会遇到另一个l2_enter入口节点
    if l1_enter == l2_enter {
        return l1_enter;
    }

    link1 = l1_enter.clone().move_step(1);
    while link1 != l1_enter {
        if link1 == l2_enter {
            return l2_enter;
        }
        link1 = link1.move_step(1);
    }

    // 3. 既不在环外相交也不在环内相交，则不会相交
    RcLink(None)
}

/// 两个单链表相交
/// 链表可能有环也可能无环；如果两个链表相交，返回相交的第一个节点；如果不相交返回None
fn list_cross(list1: RcList, list2: RcList) -> RcLink {
    let (l1_len, l1_tail, l1_enter) = list1.iter_list_hashmap();
    let (l2_len, l2_tail, l2_enter) = list2.iter_list_hashmap();
    let l1 = list1.head.clone();
    let l2 = list2.head.clone();

    // 1. 如果两条链表没有环
    if l1_enter.is_none() && l2_enter.is_none() {
        // 如果尾节点不同，说明不相交
        if l1_tail != l2_tail {
            return RcLink(None);
        }

        // 如果尾节点相同，说明相交
        return nonring_list_cross(l1, l1_len, l2, l2_len);
    }

    // 2. 如果有环
    if l1_enter.is_some() && l2_enter.is_some() {
        return ring_list_cross(l1, l1_enter, l2, l2_enter);
    }

    // 3. 一个有环一个无环，肯定不想交
    RcLink(None)
}

pub fn list2_main() {
    print!("新建链表：");
    let mut list = RcList::new();
    println!("list: {}", list);
    println!("list尾节点：{}", list.tail());
    let (len, tail, enter) = list.iter_list();
    println!(
        "[快慢指针] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = list.iter_list_hashmap();
    println!(
        "[HashMap] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );

    print!("\n加入新元素：");
    // list.push(1).push(2).push(3).push(4).push(5).push(6);
    list.push(0).push(1).push(2);
    println!("list: {}", list);
    println!("list尾节点：{}", list.tail());
    let (len, tail, enter) = list.iter_list();
    println!(
        "[快慢指针] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = list.iter_list_hashmap();
    println!(
        "[HashMap] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );

    println!("\n索引指定元素：");
    let mut l = list.idx(0);
    println!("list[0]: {}", l);
    l = list.idx(3);
    println!("list[3]: {}", l);

    println!("\n创建相交链表：");
    let mut l1 = RcList::new();
    let mut l2 = RcList::new();
    l1.push(0).push(1).push(2).push(3).push(4).push(5);
    l2.push(100).push(200);
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("\nl2.append(l1[3])");
    l2.append(&l1.idx(3));
    println!("l2: {}", l2);
    println!("l1: {}", l1);
    let (len, tail, enter) = l1.iter_list();
    println!(
        "[快慢指针] 链表l1(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = l1.iter_list_hashmap();
    println!(
        "[HashMap] 链表l1(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = l2.iter_list();
    println!(
        "[快慢指针] 链表l2(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = l2.iter_list_hashmap();
    println!(
        "[HashMap] 链表l2(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );

    println!("\n链表节点作为hashmap的键：");
    println!("map.insert(l1[3], 3)");
    let mut map = HashMap::new();
    map.insert(l1.idx(3), 3);
    let x = map.get(&l2.idx(2));
    println!("hashmap.get(l2[2]): {:?}", x);

    // 无环链表
    println!("\n无环/有环链表：");
    let mut ring = RcList::new();
    ring.push(0).push(1).push(2).push(3).push(4).push(5);
    println!("\n无环链表: {}", ring);
    println!("入环节点(集合)：{}", ring.ring_enter_hashset());
    println!("入环节点(快慢指针)：{}", ring.ring_enter());
    println!("无环链表尾结点：{}", ring.tail());
    let (len, tail, enter) = ring.iter_list();
    println!(
        "[快慢指针] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = ring.iter_list_hashmap();
    println!(
        "[HashMap] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );

    // 有环链表
    let mut ring = RcList::new();
    ring.push(0).push(1).push(2).push(3).push(4).push(5);
    ring.append(&ring.idx(3));
    println!("\n有环链表：{}", ring);
    println!("入环节点(集合)：{}", ring.ring_enter_hashset());
    println!("入环节点(快慢指针)：{}", ring.ring_enter());
    println!("有环链表尾结点：{}", ring.tail());
    let (len, tail, enter) = ring.iter_list();
    println!(
        "[快慢指针] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = ring.iter_list_hashmap();
    println!(
        "[HashMap] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );

    println!("\n随机数组加入链表：");
    let mut ring = RcList::new();
    let array = random_array(10, 0..10);
    ring.from_array(&array);
    println!("array: {:?}", array);
    println!("ring: {}", ring);
    println!("\n随机指定有环入口节点：");
    let idx = random_num(0..5) as usize;
    println!("idx: {}", idx);
    ring.append(&ring.idx(idx));
    println!("有环链表：{}", ring);
    println!("有环链表尾结点：{}", ring.tail());
    println!("有环入口节点（集合）：{}", ring.ring_enter_hashset());
    println!("有环入口节点（快慢指针）：{}", ring.ring_enter());
    let (len, tail, enter) = ring.iter_list();
    println!(
        "[快慢指针] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );
    let (len, tail, enter) = ring.iter_list_hashmap();
    println!(
        "[HashMap] 链表(len, tail, enter): {}, {}, {}",
        len, tail, enter
    );

    println!("\n判断两个有环链表是否相交");
    println!("==== 1. 两个无环链表不相交链表 ====");
    let mut l1 = RcList::new();
    l1.from_array(&[0, 1, 2, 3, 4, 5]);
    let mut l2 = RcList::new();
    l2.from_array(&[0, 1, 2, 3, 4, 5]);
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("l1 与 l2 的交点： {}", list_cross(l1, l2));

    println!("==== 2. 两个有环链表不相交链表 ====");
    let mut l1 = RcList::new();
    l1.from_array(&[0, 1, 2, 3, 4, 5]);
    l1.append(&l1.idx(3));
    let mut l2 = RcList::new();
    l2.from_array(&[0, 1, 2, 3, 4, 5]);
    l2.append(&l2.idx(2));
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("l1 与 l2 的交点： {}", list_cross(l1, l2));

    println!("==== 3. 两个无环链表相交链表 ====");
    let mut l1 = RcList::new();
    l1.from_array(&[0, 1, 2, 3, 4, 5]);
    let mut l2 = RcList::new();
    l2.from_array(&[10, 11, 1]);
    l2.append(&l1.idx(3));
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("l1 与 l2 的交点：{}", list_cross(l1, l2));

    println!("==== 4. 两个有环链表在环外相交 ====");
    let mut l1 = RcList::new();
    l1.from_array(&[0, 1, 2, 3, 4, 5, 6, 7]);
    l1.append(&l1.idx(4));
    let mut l2 = RcList::new();
    l2.from_array(&[10, 11, 12]);
    l2.append(&l1.idx(2));
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("l1 与 l2的交点：{}", list_cross(l1, l2));

    println!("==== 5. 两个有环链表在环内相交 ====");
    let mut l1 = RcList::new();
    l1.from_array(&[0, 1, 2, 3, 4, 5, 6, 7]);
    l1.append(&l1.idx(4));
    let mut l2 = RcList::new();
    l2.from_array(&[10, 11, 12]);
    l2.append(&l1.idx(5));
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("l1 与 l2的交点：{}", list_cross(l1, l2));

    println!("==== 6. 两个有环链表在环内不相交 ====");
    let mut l1 = RcList::new();
    l1.from_array(&[0, 1, 2, 3, 4, 5, 6, 7]);
    l1.append(&l1.idx(4));
    let mut l2 = RcList::new();
    l2.from_array(&[10, 11, 12, 13, 14, 15, 16, 17]);
    l2.append(&l2.idx(4));
    println!("l1: {}", l1);
    println!("l2: {}", l2);
    println!("l1 与 l2的交点：{}", list_cross(l1, l2));
}
